package com.lw.leetcode.binary.b;

/**
 * Created with IntelliJ IDEA.
 * 1898. 可移除字符的最大数目
 *
 * @author liw
 * @version 1.0
 * @date 2022/4/14 10:09
 */
public class MaximumRemovals {

    public static void main(String[] args) {
        MaximumRemovals test = new MaximumRemovals();

        // 2
        String s = "abcacb";
        String p = "ab";
        int[] arr = {3,1,0};
        int i = test.maximumRemovals(s, p, arr);
        System.out.println(i);
    }

    public int maximumRemovals(String s, String p, int[] removable) {
        char[] copy = s.toCharArray();
        char[] arr = s.toCharArray();
        char[] items = p.toCharArray();
        int end = removable.length - 1;
        int st = 0;
        while (st <= end) {
            int m = st + ((end - st + 1) >> 1);
            for (int i = 0; i <= m; i++) {
                arr[removable[i]] = ' ';
            }
            if (find(arr, items)) {
                if (st == end) {
                    break;
                }
                st = m;
            } else {
                end = m - 1;
            }
            for (int i = 0; i <= m; i++) {
                arr[removable[i]] = copy[removable[i]];
            }
        }
        return end + 1;
    }

    private boolean find (char[] arr, char[] items) {
        int m = arr.length;
        int n = items.length;
        int i = 0;
        int j = 0;
        while (i < m && j < n) {
            if (arr[i] == items[j]) {
                j++;
            }
            i++;
        }
        return n == j;
    }

}
